#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : parse_tree.py
@Time    : 2022/11/26 22:45:54
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 解析表达式
"""


import operator
from pythonds.basic import Stack
from pythonds.trees import BTree


def build_parse_tree(fpexp: str) -> BTree:
    """演示解析全括号表达式运算

    Args:
        fpexp (str): 运算表达式，各元素以空格分开。必须要要有外层括号

    Raises:
        ValueError: 运算表达式解析有误

    Returns:
        BTree: 运算表达式的解析树
    """
    fplist = fpexp.split()
    p_stack = Stack()  # BTree结果只存储了子树节点，没有存储父节点；利栈实现父节点的访问
    e_tree = BTree("")
    p_stack.push(e_tree)  # 根节点入库
    cur_tree = e_tree
    for i in fplist:
        if i == "(":
            # 如果是左括号，直接生成左子树，并将当前节点指向左子树
            cur_tree.insert_left("")
            p_stack.push(cur_tree)
            cur_tree = cur_tree.get_left_child()
        elif i not in "+-*/)":
            # 是数值，直接修改节点信息,并指回父节点
            cur_tree.set_root_val(eval(i))
            cur_tree = p_stack.pop()
        elif i in "+-*/":
            # 操作符，就修改节点内容，生成并指向右子树
            cur_tree.set_root_val(i)
            cur_tree.insert_right("")
            p_stack.push(cur_tree)
            cur_tree = cur_tree.get_right_child()
        elif i == ")":
            cur_tree = p_stack.pop()
        else:
            raise ValueError

    return e_tree


def evaluate(parse_tree: BTree):
    """以递归的方式遍历二叉树进行计算

    Args:
        parse_tree (BTree): 运算式的解析树
    """
    opers = {
        "+": operator.add,
        "-": operator.sub,
        "*": operator.mul,
        "/": operator.truediv,
    }

    # 缩小规模
    left_c = parse_tree.get_left_child()
    right_c = parse_tree.get_right_child()

    if left_c and right_c:
        fn = opers[parse_tree.get_root_val()]
        return fn(evaluate(left_c), evaluate(right_c))  # 递归节点
    else:
        return parse_tree.get_root_val()  # 基本结束条件：没有左右子树，即叶子节点


def print_expr(et: BTree) -> str:
    s = ""
    if et.get_left_child() is None and et.get_right_child() is None:
        s = f"{et.get_root_val()}"
    else:
        s = f"({print_expr(et.get_left_child())} {et.get_root_val()} {print_expr(et.get_right_child())})"
    return s


def test():
    fstr = "( ( 3 + 5 ) + ( 2 * 10 ) )"
    etree = build_parse_tree(fstr)
    print(evaluate(etree))
    print(print_expr(etree))
